home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Gamers Delight 2
/
Gamers Delight 2.iso
/
Aminet
/
game
/
board
/
Chaos53src.lha
/
chaos
/
src
/
Pairings.c
< prev
next >
Wrap
C/C++ Source or Header
|
1994-12-03
|
35KB
|
1,469 lines
/* Chaos: The Chess HAppening Organisation System V5.3
Copyright (C) 1993 Jochen Wiedmann
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
$RCSfile: Pairings.c,v $
$Revision: 3.3 $
$Date: 1994/12/03 18:02:26 $
This file contains the pairing-functions. The algorithm of the
swiss-pairing is described in the function LoseGroup().
Computer: Amiga 1200 Compiler: Dice 2.07.54 (3.0)
Author: Jochen Wiedmann
Am Eisteich 9
72555 Metzingen
Tel. 07123 / 14881
Internet: wiedmann@mailserv.zdv.uni-tuebingen.de
*/
#ifndef CHAOS_H
#include "chaos.h"
#endif
/*
This structure is used to build the groups of players with same numbers
of points.
*/
struct Group
{ struct Group *Next;
struct Player *First;
struct Player *Last;
int NumMembers;
int NumAllocMembers;
};
/*
Some functions to administrate a double-linked-list. They are close
to the corresponding Exec-functions.
*/
/*
MyRemove() removes player t from group g.
*/
void MyRemove(struct Group *g, struct Player *t)
{
if (t->LT_Pred == NULL)
{ g->First = t->LT_Succ;
}
else
{ t->LT_Pred->LT_Succ = t->LT_Succ;
}
if (t->LT_Succ == NULL)
{ g->Last = t->LT_Pred;
}
else
{ t->LT_Succ->LT_Pred = t->LT_Pred;
}
g->NumMembers--;
}
/*
MyAddTail() adds player t to the tail of group g.
*/
void MyAddTail(struct Group *g, struct Player *t)
{ if ((t->LT_Pred = g->Last) == NULL)
{ g->First = t;
}
else
{ g->Last->LT_Succ = t;
}
t->LT_Succ = NULL;
g->Last = t;
g->NumMembers++;
}
/*
MyAddHead() adds player t to the head of group g.
*/
void MyAddHead(struct Group *g, struct Player *t)
{ if ((t->LT_Succ = g->First) == NULL)
{ g->Last = t;
}
else
{ g->First->LT_Pred = t;
}
t->LT_Pred = NULL;
g->First = t;
g->NumMembers++;
}
/*
MyInsert() inserts player t into group g after player pred.
Note, that pred may be null, in which case MyAddHead() is called.
*/
void MyInsert(struct Group *g, struct Player *t, struct Player *pred)
{ if (pred == NULL)
{ MyAddHead(g, t);
}
else
{ if (pred->LT_Succ == NULL)
{ MyAddTail(g, t);
}
else
{ t->LT_Succ = pred->LT_Succ;
t->LT_Pred = pred;
pred->LT_Succ->LT_Pred = t;
pred->LT_Succ = t;
g->NumMembers++;
}
}
}
/*
MyEnqueue() inserts player t into group g. The group is sorted by the
player->Nr fields.
*/
void MyEnqueue(struct Group *g, struct Player *t)
{ struct Player *succ;
for (succ = g->First; succ != NULL; succ = succ->LT_Succ)
{ if (t->Nr < succ->Nr)
{ break;
}
}
if (succ == NULL)
{ MyAddTail(g, t);
}
else
{ MyInsert(g, t, succ->LT_Pred);
}
}
/*
GameAddress() returns the address of a game-structure.
Inputs: t - player, whose game list will be searched
r - number of the round, which's game structure will be
returned. This may be 0, in which case the address of
t->First_Game will be returned.
Result: pointer to the game structure corresponding to player t, round r
*/
struct Game *GameAddress(struct Player *t, int r)
{ struct Game *g;
for (g = (struct Game *) &(t->First_Game); r != 0;
g = g->Next, r--)
{
}
return(g);
}
/*
The NewGames() function gets called after each round that has been
paired. It assumes, that each players Opponent, GFlags and BoardNr fields
are initialized.
Inputs: memlistptr - pointer to the memory list, where the allocated
memory will be included.
fpoints - number of points, that free players will receive
(2 for swiss pairing, 0 for round robin)
Result: TRUE, if successful, FALSE otherwise
*/
static int NewGames(void **memlistptr, int fpoints)
{ struct Game *g, *gmem;
struct Player *t;
int NumGames = 0;
/*
Allocate new game structures.
*/
if ((gmem = GetMem(memlistptr, sizeof(*g)*NumPlayers)) == NULL)
{ return(FALSE);
}
NumRounds++;
/*
Initialize the game structures.
*/
for (t = ((struct Player *) PlayerList.lh_Head), g = gmem;
t->Tn_Node.ln_Succ != NULL;
t = (struct Player *) t->Tn_Node.ln_Succ, g++)
{ if (t->Flags & TNFLAGSF_WITHDRAWN)
{ t->GFlags |= GMFLAGSF_NOFIGHT;
}
else if (t->Opponent == NULL)
{ t->GFlags |= GMFLAGSF_NOFIGHT|GMFLAGSF_POINTFORFREE;
}
GameAddress(t, NumRounds-1)->Next = g;
g->Next = NULL;
g->Opponent = t->Opponent;
g->Flags = t->GFlags;
g->BoardNr = t->BoardNr;
if (g->Flags & GMFLAGSF_NOFIGHT)
{ if (t->Flags & TNFLAGSF_WITHDRAWN)
{ g->Result = 0;
g->Flags = GMFLAGSF_WITHDRAWN;
}
else
{ t->Points += fpoints;
g->Result = fpoints;
t->Flags |= TNFLAGSF_HADFREE;
}
}
else
{ NumGames++;
g->Result = -1;
if (g->Flags & GMFLAGSF_WHITE)
{ t->HowMuchWhite++;
if (t->HowMuchWhiteLast > 0)
{ t->HowMuchWhiteLast++;
}
else
{ t->HowMuchWhiteLast = 1;
}
}
else
{ t->HowMuchWhite--;
if (t->HowMuchWhiteLast < 0)
{ t->HowMuchWhiteLast--;
}
else
{ t->HowMuchWhiteLast = -1;
}
}
}
}
NumGamesMissing = NumGames/2;
return(TRUE);;
}
/*
The function CreateRankings() creates the internal ranking list.
The list is sorted by ELO numbers (if players have one) and by DWZ
numbers otherwise.
Players without rating number will appear at the tail of the list
*/
void CreateRankings(void)
{ struct Player *t, **tptr;
int t1, t2;
RankingFirst = NULL;
for (t = (struct Player *) PlayerList.lh_Head;
t->Tn_Node.ln_Succ != NULL;
t = (struct Player *) t->Tn_Node.ln_Succ)
{ /*
Get the curremt players (t) rating number into t1.
*/
if ((t1 = t->ELO) == 0)
{ t1 = tdwz(t);
}
/*
Insert t into the internal ranking list
*/
for (tptr = &RankingFirst; *tptr != NULL;
tptr = &((*tptr)->RankNext))
{ if (t1 != 0)
{ if ((t2 = (*tptr)->ELO) == 0)
{ t2 = tdwz(*tptr);
}
if (t1 > t2)
{ break;
}
}
}
t->RankNext = *tptr;
*tptr = t;
}
}
/*
DoSwissPairingFirst() makes the pairings of the first round of a
Swiss pairing tournament.
Inputs: user - True, if the user may set games
*/
static int DoSwissPairingFirst(int user)
{ struct Player *t, *thelp;
int NumGames, NumFreePlayers;
int i, j;
int flag;
int BoardNr;
/*
Build the internal ranking list
*/
CreateRankings();
/*
Allow the user to make settings.
*/
if ((BoardNr = GetSettings(user)) == -1)
{ return(FALSE);
}
#ifdef DEBUG_PAIRINGS
printf("Setting results:\n");
for (t = RankingFirst; t != NULL; t = t->RankNext)
{ if (t->Opponent)
{ printf("Player %s paired against %s.\n", t->Name, t->Opponent->Name);
}
else if (t->GFlags & GMFLAGSF_NOFIGHT)
{ printf("One point bye: %s\n", t->Name);
}
else
{ printf("Player %s not set\n", t->Name);
}
}
#endif
/*
get colour of player 1
*/
flag = (RangeRand(2) == 0) ? GMFLAGSF_WHITE : 0;
/*
Count the number of players without opponent. Get the number of players
with minimal rating. Additionally setup the colors for set players.
*/
NumFreePlayers = 0;
for (t = RankingFirst; t != NULL; t = t->RankNext)
{ if (t->Opponent == NULL && (t->GFlags & GMFLAGSF_NOFIGHT) == 0)
{ NumFreePlayers++;
}
else if (t->Opponent)
{ if ((t->GFlags & GMFLAGSF_WHITE) == 0 &&
(t->Opponent->GFlags & GMFLAGSF_WHITE) == 0)
{ t->GFlags = flag;
flag = GMFLAGSF_WHITE - flag;
t->Opponent->GFlags = flag;
}
#ifdef DEBUG_PAIRINGS
printf("Game set: %s : %s (%d)\n",
flag ? t->Opponent->Name : t->Name,
flag ? t->Name : t->Opponent->Name, BoardNr);
}
else
{ printf("One point bye set: %s\n", t->Name);
#endif
}
}
/*
If the number of free players is odd, select a player which receives a
one point bye.
*/
#ifdef DEBUG_PAIRINGS
printf("Number of players not set: %d\n", NumFreePlayers);
#endif
if (NumFreePlayers % 2)
{ int i, ihelp;
/*
Find the 5 players with the lowest ranking.
*/
int MinPlayers = (NumFreePlayers > 5) ? 5 : NumFreePlayers;
i = ihelp = NumFreePlayers;
t = thelp = RankingFirst;
for (t = thelp = RankingFirst; t != NULL; t = t->RankNext)
{ if (t->Opponent == NULL)
{ if (thelp->Opponent != NULL)
{ thelp = t;
ihelp = i;
}
if (tdwz(t) < tdwz(thelp))
{ if (i >= MinPlayers)
{ thelp = t;
ihelp = i;
}
}
--i;
}
}
#ifdef DEBUG_PAIRINGS
printf("Looking for one point bye beginning with %s.\n", thelp->Name);
#endif
/*
Now thelp points to the last ihelp players. Select one of them.
*/
j = RangeRand(ihelp);
while(j > 0 || thelp->Opponent)
{ if (!thelp->Opponent)
{ --j;
}
thelp = thelp->RankNext;
}
#ifdef DEBUG_PAIRINGS
printf("Player %s gets a one point bye.\n", thelp->Name);
#endif
thelp->GFlags = GMFLAGSF_POINTFORFREE|GMFLAGSF_NOFIGHT;
--NumFreePlayers;
}
/*
Do the other pairings. t points into the upper and thelp into the
lower half of the players.
*/
if ((NumGames = NumFreePlayers/2))
{ /*
Initialize thelp
*/
thelp = RankingFirst;
for (i = NumGames; i; thelp = thelp->RankNext)
{ if (thelp->Opponent == NULL &&
(thelp->GFlags & GMFLAGSF_NOFIGHT) == 0)
{ i--;
}
}
for (t = RankingFirst, i = NumGames; i; --i)
{
#ifdef DEBUG_PAIRINGS
printf("Looking for next game: Upper half player %s, lower half player %s\n",
t->Name, thelp->Name);
#endif
/*
t and thelp must not point on free or set players!
*/
while ((t->GFlags & GMFLAGSF_NOFIGHT) != 0 ||
t->Opponent != NULL)
{ t = t->RankNext;
}
while ((thelp->GFlags & GMFLAGSF_NOFIGHT) != 0 ||
thelp->Opponent != NULL)
{ thelp = thelp->RankNext;
}
t->Opponent = thelp;
thelp->Opponent = t;
t->BoardNr = ++BoardNr;
thelp->BoardNr = BoardNr;
t->GFlags = flag;
flag = GMFLAGSF_WHITE - flag;
thelp->GFlags = flag;
#ifdef DEBUG_PAIRINGS
printf("Pairing %s : %s (%d)\n",
flag ? thelp->Name : t->Name,
flag ? t->Name : thelp->Name, t->BoardNr);
#endif
t = t->RankNext;
thelp = thelp->RankNext;
}
}
return(TRUE);
}
/*
GamePossible() checks, if two players may be paired.
*/
int GamePossible(struct Player *t1, struct Player *t2)
{ struct Game *g;
#ifdef DEBUG_PAIRINGS
printf("Trying players %s and %s:", t1->Name, t2->Name);
#endif
if (t1 == t2 ||
(t1->HowMuchWhiteLast >= 2 && t2->HowMuchWhiteLast >= 2) ||
(t1->HowMuchWhiteLast <= -2 && t2->HowMuchWhiteLast <= -2))
{
#ifdef DEBUG_PAIRINGS
printf("Colors don't match.\n");
#endif
return(FALSE);
}
for (g = t1->First_Game; g != NULL; g = g->Next)
{
if (g->Opponent == t2)
{
#ifdef DEBUG_PAIRINGS
printf("Paired already.\n");
#endif
return(FALSE);
}
}
#ifdef DEBUG_PAIRINGS
printf("Ok\n");
#endif
return(TRUE);
}
/*
The DoGame() function looks for a game in the actual group.
Inputs: g - group in which should be looked
t - player, who should get an opponent
BoardNr - number of the first board that isn't used
MayChangeColors - number of allowed pairings in the same color
group
MayGoUpperHalf - number of allowed pairings in the same (upper
or lower) half
MayGoDown - number players that may be left (1, if the
number of players in the group is odd)
Results: 0 = No pairings possible, terminate
1 = Successfull finish, terminate
-1 = The lower groups could not be paired and this is a group
with an even number of players. Put one into the next!
*/
static int DoGroup(struct Group *);
static int DoGame(struct Group *g, struct Player *t,
int MayChangeColors, int MayGoUpperHalf, int MayGoDown)
{ struct Player *tg, *thelp, *LowerHalf;
int result;
int IsLowerHalf, i;
switch (g->NumMembers-g->NumAllocMembers)
{ /*
Only one player left? Put him into the next group or give him
a point for free if there are no lower groups.
*/
case 1:
/*
Look for free player
*/
for (t = g->First; t->Opponent != NULL; t = t->LT_Succ)
{
}
if (g->Next == NULL)
{ if (t->Flags & TNFLAGSF_HADFREE)
{ return(0);
}
t->GFlags |= GMFLAGSF_POINTFORFREE|GMFLAGSF_NOFIGHT;
return(1);
}
if (t->Flags & TNFLAGSF_NOTDOWN)
{ return (FALSE);
}
thelp = t->LT_Pred;
MyRemove(g, t);
MyEnqueue(g->Next, t);
if ((result = DoGroup(g->Next)) == FALSE)
/*
Remember, that it doesn't help to put this player into the next
group.
*/
{ t->Flags |= TNFLAGSF_NOTDOWN;
}
MyRemove(g->Next, t);
MyInsert(g, t, thelp);
return(result);
/*
Group finished? On to the next! If not successfull now, we need
to change the group!
*/
case 0:
return((DoGroup(g->Next) == 0) ? -1 : 1);
/*
We still need to do some pairings in this group. Sigh!
*/
default:
/*
Looking for a player without opponent.
*/
while (t->Opponent != NULL)
{ t = t->LT_Succ;
}
/*
We must not look for opponents in the upper half, if this player
is from the lower half! So check, if he is.
*/
IsLowerHalf = TRUE;
LowerHalf = g->First;
i = (g->NumMembers/2);
do
{ if (LowerHalf == t)
{ IsLowerHalf = FALSE;
}
LowerHalf = LowerHalf->LT_Succ;
}
while(--i);
/*
Try to get an opponent in the lower half with different colors.
*/
for (tg = IsLowerHalf ? t->LT_Succ : LowerHalf; tg != NULL;
tg = tg->LT_Succ)
{ if (tg->Opponent == NULL &&
t->HowMuchWhiteLast*tg->HowMuchWhiteLast <= 0 &&
GamePossible(t, tg))
{ /*
Try this pairing
*/
t->Opponent = tg;
tg->Opponent = t;
g->NumAllocMembers += 2;
/*
Check if the remaining players may get paired.
*/
if ((result = DoGame(g, t->LT_Succ,
MayChangeColors, MayGoUpperHalf, MayGoDown))
!= 0)
{ return(result);
}
/*
They don't, so undo this pairing.
*/
g->NumAllocMembers -= 2;
t->Opponent = tg->Opponent = NULL;
}
}
/*
Looking for an opponent in the lower half without changing the
colors. (If it is allowed!)
*/
if (MayChangeColors != 0)
{ for (tg = IsLowerHalf ? t->LT_Succ : LowerHalf; tg != NULL;
tg = tg->LT_Succ)
{ if (tg->Opponent == NULL &&
t->HowMuchWhiteLast*tg->HowMuchWhiteLast > 0 &&
GamePossible(t, tg))
{ /*
Try this pairing
*/
t->Opponent = tg;
tg->Opponent = t;
g->NumAllocMembers += 2;
/*
Check if the remaining players may get paired.
*/
if ((result = DoGame(g, t->LT_Succ, MayChangeColors-1,
MayGoUpperHalf, MayGoDown))
!= 0)
{ return(result);
}
/*
They don't, so undo this pairing.
*/
g->NumAllocMembers -= 2;
t->Opponent = tg->Opponent = NULL;
}
}
}
/*
Looking for an opponent in the upper half with different colors.
(If it is allowed!)
*/
if (MayGoUpperHalf != 0)
{ for (tg = IsLowerHalf ? NULL : LowerHalf->LT_Pred;
tg != NULL && tg != t; tg = tg->LT_Pred)
{ if(tg->Opponent == NULL &&
t->HowMuchWhiteLast*tg->HowMuchWhiteLast <= 0 &&
GamePossible(t, tg))
{ /*
Try this pairing
*/
t->Opponent = tg;
tg->Opponent = t;
g->NumAllocMembers += 2;
/*
Check if the remaining players may get paired.
*/
if ((result = DoGame(g, t->LT_Succ, MayChangeColors,
MayGoUpperHalf-1, MayGoDown))
!= 0)
{ return(result);
}
/*
They don't, so undo this pairing.
*/
g->NumAllocMembers -= 2;
t->Opponent = tg->Opponent = NULL;
}
}
}
/*
Finally looking for an opponent in the upper half without
changing colors. Do we really need this? Arrgl! (It would not be
allowed otherwise.)
*/
if (MayChangeColors != 0 && MayGoUpperHalf != 0)
{ for (tg = IsLowerHalf ? NULL : LowerHalf->LT_Pred;
tg != NULL && tg != t; tg = tg->LT_Pred)
{ if(tg->Opponent == NULL &&
t->HowMuchWhiteLast*tg->HowMuchWhiteLast > 0 &&
GamePossible(t, tg))
{ /*
Try this pairing
*/
t->Opponent = tg;
tg->Opponent = t;
g->NumAllocMembers += 2;
/*
Check if the remaining players may get paired.
*/
if ((result = DoGame(g, t->LT_Succ, MayChangeColors-1,
MayGoUpperHalf-1, MayGoDown))
!= 0)
{ return(result);
}
/*
They don't, so undo this pairing.
*/
g->NumAllocMembers -= 2;
t->Opponent = tg->Opponent = NULL;
}
}
}
/*
The LAST possibility is to drop one player, who will finally
get moved into the next group.
*/
if (MayGoDown)
{ return(DoGame(g, t->LT_Succ, MayChangeColors,
MayGoUpperHalf, 0));
}
}
/*
Nothing helps. We cannot pair the remaining members of this group.
Give up!
*/
return(0);
}
/*
The DoGroup() function is the main function to do the Swiss pairing.
It pairs the member of one group of players (Usually the players with
the same number of points.) and calls itself for the next group, if
possible.
Inputs: g - the group to pair
Results: 1 = Success, finish!
0 = The group could not be paired, so the higher groups need
to be rearranged.
The algorithm depends on the rules from the "Turnierleiterhandbuch des
Deutschen Schachbundes" (The official german chess federation's guide
to managing chess-tournaments). But this rules aren't quite clear and
especially not definite. For example i don't see what should happen,
if some players with the same number of points are leading, but have
already been paired against each other.
The pairing begins with collecting the players in groups of members
with the same number of points. These groups are used to build the new
internal ranking list. Players of one group are ordered by the previous
list and by the official lists in the first round. DoGroup() gets called
for the highest group, if successfull for the next group and so on.
But how to pair the group-members? We begin with splitting the members
in an upper and a lower half. (The lower has possibly one member more,
if the number of group-members is odd.) Both halfs get splitted again,
depending on their last color. Example: (The players to the left had
white in the last round.)
Upper Half: 1 3
2
Lower Half: 4 5
7 6
DoGame() gets called to find an opponent for player 1. We try player 5
and next player 6. DoGame() calls itself for an opponent of player 2,
if successfull. If it is successfull again, it calls itself for the third
time, to find an opponent for player 3. When 3 games have been found,
this group is done and we move the remaining player into the next group
and call DoGroup() for it.
But possibly it isn't possible to pair the players in that way. In that
case we need to allow some things that we don't like very much: Pairing
opponents of the same color (1-4), pairing opponents from the upper half
(1-3) or dropping players which will get moved into the next group
then. The variables MayChangeColors, MayGoUpperHalf and MayGoDown tell
us, what is allowed.
A game is possible, if
a) The same players haven't already been paired
b) No opponent has the same color for the third time (However, it
is allowed to have four times black in 5 rounds! Not my choice,
i follow the guide mentioned above.)
c) the remaining players may be paired and a) and b) holds still
for them
*/
static int DoGroup(struct Group *g)
{ struct Player *t;
int result;
int MayChangeColors, MayGoUpperHalf, MayGoDown;
#ifdef DEBUG_PAIRINGS
/*
Print the list of group members.
*/
{ extern struct Group *FirstGroup;
struct Group *myg;
struct Player *myt;
for (myg = FirstGroup; myg != NULL; myg = myg->Next)
{ printf("(");
for(myt = myg->First; myt != NULL; myt = myt->LT_Succ)
{ if (myt != myg->First)
{ printf(",");
}
printf("%s", myt->Name);
}
printf(")");
}
printf("\n");
}
#endif
/*
Looking for a nonempty group (Not sure, if this might happen, but
does no harm!
*/
while(g != NULL && g->NumMembers == 0)
{ g = g->Next;
}
if (g == NULL)
{ return(1);
}
/*
Remove the TNFLAGSF_NOTDOWN flag from all group members. (They might
have received it sooner.)
*/
for(t = g->First; t != NULL; t = t->LT_Succ)
{ t->Flags &= ~TNFLAGSF_NOTDOWN;
}
/*
We begin with allowing NOTHING and slowly a little bit more...
(I would be glad, if any body knew a faster solution!)
*/
MayGoDown = 0;
do
{ MayGoUpperHalf = 0;
do
{ MayChangeColors = 0;
do
{ switch (DoGame(g, g->First, MayChangeColors, MayGoUpperHalf,
MayGoDown))
{ case 1:
/*
Success!
*/
return(1);
case -1:
/*
The following groups cannot be paired! Senseless to pair this
group. Undo all pairings and change the group.
*/
for (t = g->First; t != NULL; t = t->LT_Succ)
{ t->Opponent = NULL;
}
g->NumAllocMembers = 0;
goto changegroup;
}
}
while (++MayChangeColors <= g->NumMembers/2);
}
while (++MayGoUpperHalf <= g->NumMembers/4);
}
while (++MayGoDown <= g->NumMembers % 2);
changegroup:
/*
It isn't possible, to pair this group. The last possibility is to
move one player into the next and retry. (DoGame() has already done
this, if there is only one member.)
*/
if (g->Next != NULL && g->NumMembers != 1)
{ t = g->Last;
MyRemove(g, t);
MyEnqueue(g->Next, t);
result = DoGroup(g);
if (result)
{ return(TRUE);
}
MyRemove(g->Next, t);
MyAddTail(g, t);
}
/*
Doesn't help! We have failed!
*/
return(FALSE);
}
/*
The DoSwissPairing() function gets called instead of
DoSwissPairingFirst() for round 2 and later.
Inputs: user - TRUE, if the user may set games
Result: TRUE, if succesfull, FALSE otherwise
*/
#ifdef DEBUG_PAIRINGS
struct Group *FirstGroup;
#endif
static int DoSwissPairing(int user)
{ struct Player *t, *thelp, **tptr;
struct Group *g, **gptr;
void *PKey = NULL;
short gpoints;
int BoardNr;
int i, result;
#ifndef DEBUG_PAIRINGS
struct Group *FirstGroup;
#endif
FirstGroup = NULL;
/*
First create the new ranking list
*/
t = RankingFirst;
RankingFirst = NULL;
while (t != NULL)
{ for (tptr = &RankingFirst; *tptr != NULL;
tptr = &((*tptr)->RankNext))
{ if (t->Points > (*tptr)->Points)
{ break;
}
}
thelp = t->RankNext;
t->RankNext = *tptr;
*tptr = t;
t = thelp;
}
#ifdef DEBUG_PAIRINGS
{ int i;
printf("New rankings:\n");
for (i = 1, t = RankingFirst; t != NULL; t = t->RankNext, ++i)
{ printf("%5d. %s\n", i, t->Name);
}
}
#endif
/*
Allow the user to make settings.
*/
if ((BoardNr = GetSettings(user)) == -1)
{ return(FALSE);
}
/*
Create the groups of players with the same number of points
*/
gpoints = -1; /*
Force initialization of g and gpoints in the following
loop.
*/
gptr = &FirstGroup;
i = 0;
for (t = RankingFirst; t != NULL; t = t->RankNext)
{ t->Nr = i++;
if (t->Flags & TNFLAGSF_WITHDRAWN || t->Opponent != NULL ||
t->GFlags & GMFLAGSF_NOFIGHT)
{ continue;
}
if (gpoints != t->Points) /* Create new group */
{ if ((g = GetMem(&PKey, sizeof(*g))) == NULL)
{ PutMemList(&PKey);
return(FALSE);
}
*gptr = g;
gptr = &(g->Next);
gpoints = t->Points;
}
MyAddTail(g, t);
}
#ifdef AMIGA
set(App, MUIA_Application_Sleep, TRUE);
#endif
result = DoGroup(FirstGroup);
#ifdef AMIGA
set(App, MUIA_Application_Sleep, FALSE);
#endif
if (!result)
{ ShowError((char *) GetChaosString(MSG_NO_PAIRING));
PutMemList(&PKey);
return(FALSE);
}
/*
Select colors
*/
for (t = RankingFirst; t != NULL; t = t->RankNext)
{ if (t->Flags & TNFLAGSF_WITHDRAWN)
{ continue;
}
if (t->Opponent == NULL)
{ t->GFlags = GMFLAGSF_POINTFORFREE|GMFLAGSF_NOFIGHT;
}
else
{ /*
Select colors
*/
thelp = t->Opponent;
if ((t->GFlags & GMFLAGSF_WHITE) == 0 &&
(thelp->GFlags & GMFLAGSF_WHITE) == 0)
{ if (t->HowMuchWhiteLast < thelp->HowMuchWhiteLast ||
(t->HowMuchWhiteLast == thelp->HowMuchWhiteLast &&
(t->HowMuchWhite < thelp->HowMuchWhite ||
(t->HowMuchWhite == thelp->HowMuchWhite &&
t->Nr > thelp->Nr))))
{ thelp = t;
}
thelp->GFlags = GMFLAGSF_WHITE;
}
}
}
return(TRUE);
}
/*
DoRoundRobin() does the Round Robin pairings. Here all rounds are paired
at once.
Inputs: mode - 0 for FIDE system, TNMODEF_SHIFT_SYSTEM for shift system
Result: TRUE, if successfull, FALSE otherwise
*/
static int DoRoundRobin(int mode)
{ struct Player *t, **ttab, *tg;
struct Group g;
int i, j, k, l;
int NumGames;
int GamesMissing = 0;
short flag, BoardNr;
void *PMem = NULL, *GMem = NULL;
/*
Allocate a table of player numbers
*/
if ((ttab = GetMem(&PMem, sizeof(*ttab)*NumPlayers)) == NULL)
{ return(FALSE);
}
/*
Give any player a different number
*/
g.First = g.Last = NULL;
g.NumMembers = 0;
for (t = (struct Player *) PlayerList.lh_Head;
t->Tn_Node.ln_Succ != NULL;
t = (struct Player *) t->Tn_Node.ln_Succ)
{ MyAddTail(&g, t);
}
while (g.NumMembers > 0)
{ i = RangeRand(g.NumMembers);
for (t = g.First; i > 0; i--, t = t->LT_Succ)
{
}
t->Nr = g.NumMembers;
MyRemove(&g, t);
ttab[g.NumMembers] = t;
}
NumGames = (NumPlayers+1)/2;
if ((mode & TNMODEF_SHIFT_SYSTEM) == 0)
{ /*
Here comes the FIDE-system.
Assume n=NumPlayers (n=NumPlayers+1 for an odd number of players)
The FIDE system wants the following pairings for round 1:
1:n, 2:n-1, 3:n-2, 4:n-3 and so on. (n as opponent means free round,
if the number of players is odd.)
*/
for (i = 0; i < NumGames; i++)
{ t = ttab[i];
if(i == 0 && ((NumPlayers%2) != 0)) /* Spielfrei */
{ t->Opponent = NULL;
t->BoardNr = i;
t->GFlags = GMFLAGSF_POINTFORFREE|GMFLAGSF_NOFIGHT;
}
else
{ tg = ttab[NumGames*2-i-1];
t->Opponent = tg;
tg->Opponent = t;
t->BoardNr = tg->BoardNr = i+1;
t->GFlags = GMFLAGSF_WHITE;
tg->GFlags = 0;
GamesMissing++;
}
}
if (!NewGames(&GMem, 0))
{ goto Error;
}
/*
The following rounds are determined by a simple algorithm:
(See Ernst Schubart, Helmut Noettger: "Turnierleiterhandbuch des
Deutschen Schachbundes" (The official german chess federation's
guide to managing chess-tournaments), p.64
- In the odd rounds the players 1, 2, 3 and so on have player n as
opponent (or have a free round, if the number of players is even.
In the even rounds n plays against k+1, k+2, k+3 and so on, where
k=n/2.
- All other participants play against the player whose number is the
number of their last opponent, incremented by 1. Player n is left
out, player 1 comes after n-1.
- If the number of players is even, the players 1, 2, ..., k have
white, when playing against opponent n. The other players have
black in that case.
- In all other games the player with the lower number has the white
pieces, if the sum of the two player-numbers is odd. Otherwise he
gets the black pieces.
*/
for (j = 1; j < NumGames*2-1; j++)
{ /*
First get an opponent for player n.
*/
k = (((j%2) == 0) ? 0 : NumGames) + j/2 + 1;
t = ttab[k-1];
if ((NumPlayers%2) == 0) /* No point for free */
{ tg = ttab[NumPlayers-1];
t->BoardNr = tg->BoardNr = BoardNr = 0;
t->GFlags = (t->Nr <= NumGames) ? GMFLAGSF_WHITE : 0;
tg->GFlags = GMFLAGSF_WHITE - t->GFlags;
tg->Opponent = t;
GamesMissing++;
}
else
{ tg = NULL;
t->BoardNr = BoardNr = -1;
t->GFlags = GMFLAGSF_POINTFORFREE|GMFLAGSF_NOFIGHT;
}
t->Opponent = tg;
/*
Get the other games
*/
for (i = 1; i < NumGames; i++)
{ if (++k == NumGames*2)
{ k = 1;
}
t = ttab[k-1];
if ((tg = GameAddress(t, j)->Opponent) == NULL ||
tg->Nr == NumGames*2)
{ l = t->Nr;
}
else
{ l = tg->Nr;
}
if (++l == NumGames*2)
{ l = 1;
}
tg = ttab[l-1];
flag = (((t->Nr+tg->Nr) % 2) != 0) ? GMFLAGSF_WHITE : 0;
if (t->Nr > tg->Nr)
{ flag = GMFLAGSF_WHITE-flag;
}
t->GFlags = flag;
tg->GFlags = GMFLAGSF_WHITE-flag;
t->BoardNr = tg->BoardNr = ++BoardNr;
t->Opponent = tg;
tg->Opponent = t;
GamesMissing++;
}
if (!NewGames(&GMem, 0))
{ goto Error;
}
}
}
else
{ /*
Here comes the shift system. Its algorithm is rather easy, if you
have seen it in practice.
The boards are placed reverted on the table and all players sit down
for the first round in the following order:
1 : k
2 : k+1
3 : k+2
.
.
.
k-1 : n
(We assume again, that n is the number of players is even and
k = n/2. If this isn't true, we add a virtual player n. Playing
against n means having a free game.)
After each round the players 1, 2, 3, ..., n-1 are shifted clockwise.
All boards remain unchanged, except for the board of player n, who
may keep his place, but has to revert his board.
Below the array ttab is used to simulate the table. (That's probably
why it's got his name...)
*/
int lastflag;
for (i = 0; i < NumGames*2-1; i++)
{ for (j = 0, flag = GMFLAGSF_WHITE; j < NumGames; j++)
{ t = ttab[j];
if (j+NumGames < NumPlayers)
{ tg = ttab[j+NumGames];
t->GFlags = flag;
flag = GMFLAGSF_WHITE-flag;
tg->GFlags = flag;
tg->Opponent = t;
tg->BoardNr = j+1;
}
else
{ tg = NULL;
}
t->Opponent = tg;
t->BoardNr = j+1;
}
if (i == 0)
{ lastflag = flag;
}
else if (NumPlayers == NumGames*2)
{ t = ttab[NumGames-1];
tg = ttab[NumGames*2-1];
t->GFlags = lastflag;
lastflag = GMFLAGSF_WHITE-lastflag;
tg->GFlags = lastflag;
}
if (!NewGames(&GMem, 0))
{ goto Error;
}
/*
Shift all players except for n.
*/
t = ttab[0];
for (j = 0; j < NumGames-1; j++)
{ ttab[j] = ttab[j+1];
}
ttab[NumGames-1] = ttab[NumGames*2-2];
for (j = NumGames*2-3; j >= NumGames; j--)
{ ttab[j+1] = ttab[j];
}
ttab[NumGames] = t;
}
}
PutMem(ttab);
MoveMemList(&GMem, &TrnMem);
NumGamesMissing = GamesMissing;
return(TRUE);
Error:
for (t = (struct Player *) PlayerList.lh_Head;
t->Tn_Node.ln_Succ != NULL;
t = (struct Player *) t->Tn_Node.ln_Succ)
{ t->First_Game = NULL;
}
PutMemList(&GMem);
PutMem(ttab);
NumRounds = 0;
return(FALSE);
}
/*
This function selects the boards, where the players should play.
*/
static void SelectBoards(void)
{ struct Player *p;
int BoardNr;
for (p = RankingFirst; p != NULL; p = p->RankNext)
{ p->BoardNr = -1;
}
for (p = RankingFirst, BoardNr = 0; p != NULL; p = p->RankNext)
{ if (p->BoardNr < 0 && p->Opponent != NULL)
{ p->BoardNr = p->Opponent->BoardNr = BoardNr++;
}
}
}
/*
DoPairings() is the function that gets called from the menu.
Input: mode - tournament mode (TNMODEF_SWISS_PAIRING or
TNMODEF_ROUND_ROBIN with or without TNMODEF_SHIFT_SYSTEM)
save - TRUE, if the user should be asked to save the tournament
user - TRUE, if the user may set games (ignored for Round
Robin tournaments)
Result: TRUE, if successfull, FALSE otherwise
*/
int DoPairings(int mode, int save, int user)
{ struct Player *t, *rankingfirst;
char *name;
char trnfilename[TRNFILENAME_LEN+1];
char ending[20];
int len, endlen, oldNumRounds = NumRounds;
/*
Copy the ranking pointers. This allows to undo the pairing calls, if
something goes wrong. Additionally the Opponent and GFlags fields
get initialized.
*/
rankingfirst = RankingFirst;
for (t = (struct Player *) PlayerList.lh_Head;
t->Tn_Node.ln_Succ != NULL;
t = (struct Player *) t->Tn_Node.ln_Succ)
{ t->Helpptr = t->RankNext;
t->Opponent = NULL;
t->GFlags = 0;
}
if (mode & TNMODEF_SWISS_PAIRING)
{ if (!((NumRounds == 0) ? DoSwissPairingFirst(user) :
DoSwissPairing(user)))
{ goto Error;
}
SelectBoards();
NewGames(&TrnMem, WinnerPoints);
}
else
{ if (!DoRoundRobin(mode))
{ goto Error;
}
}
TrnMode |= mode;
IsSaved = FALSE;
/*
Offer the user to save data. If the convention "name.roundnumber.cdat"
was kept until now, we keep this.
*/
if (save)
{ strcpy(trnfilename, TrnFileName);
sprintf(ending, ".%d.cdat", oldNumRounds);
endlen = strlen(ending);
len = strlen(trnfilename);
if (len >= endlen &&
Stricmp((STRPTR) trnfilename+(len-endlen), (STRPTR) ending) == 0)
{ sprintf(trnfilename+(len-endlen), ".%d.cdat", NumRounds);
}
name = FileRequest(trnfilename, NULL, NULL, TRUE);
if (name != NULL && *name != '\0')
{ return(SaveTournament(name));
}
}
return(TRUE);;
Error:
/*
Get the old ranking list
*/
RankingFirst = rankingfirst;
for (t = (struct Player *) PlayerList.lh_Head;
t->Tn_Node.ln_Succ != NULL;
t = (struct Player *) t->Tn_Node.ln_Succ)
{ t->RankNext = t->Helpptr;
}
return(FALSE);
}